1. Field of the Invention
The present invention relates in general to the field of multithreaded processors, and particularly to instructions for generating new threads of execution in a multithreaded processor.
2. Background Art
Microprocessor designers employ many techniques to increase their performance. Most microprocessors operate using a clock signal running at a fixed frequency. Each clock cycle the circuits of the microprocessor perform their respective functions. According to Hennessy and Patterson, the true measure of a microprocessor's performance is the time required to execute a program or collection of programs. From this perspective, the performance of a microprocessor is a function of its clock frequency, the average number of clock cycles required to execute an instruction (or alternately stated, the average number of instructions executed per clock cycle), and the number of instructions executed in the program or collection of programs. Semiconductor scientists and engineers are continually making it possible for microprocessors to run at faster clock frequencies, chiefly by reducing transistor size, resulting in faster switching times. The number of instructions executed is largely fixed by the task to be performed by the program, although it is also affected by the instruction set architecture of the microprocessor. Large performance increases have been realized by architectural and organizational notions that improve the instructions per clock cycle, in particular by notions of parallelism.
One notion of parallelism that has improved the instructions per clock cycle, as well as the clock frequency, of microprocessors is pipelining, which overlaps execution of multiple instructions within pipeline stages of the microprocessor. In an ideal situation, each clock cycle one instruction moves down the pipeline to a new stage, which performs a different function on the instructions. Thus, although each individual instruction takes multiple clock cycles to complete, because the multiple cycles of the individual instructions overlap, the average clocks per instruction is reduced. The performance improvements of pipelining may be realized to the extent that the instructions in the program permit it, namely to the extent that an instruction does not depend upon its predecessors in order to execute and can therefore execute in parallel with its predecessors, which is commonly referred to as instruction-level parallelism. Another way in which instruction-level parallelism is exploited by contemporary microprocessors is the issuing of multiple instructions for execution per clock cycle, commonly referred to as superscalar microprocessors.
What has been discussed above pertains to parallelism at the individual instruction-level. However, the performance improvement that may be achieved through exploitation of instruction-level parallelism is limited. Various constraints imposed by limited instruction-level parallelism and other performance-constraining issues have recently renewed an interest in exploiting parallelism at the level of blocks, or sequences, or streams of instructions, commonly referred to as thread-level parallelism. A thread is simply a sequence, or stream, of program instructions. A multithreaded microprocessor concurrently executes multiple threads according to some scheduling policy that dictates the fetching and issuing of instructions of the various threads, such as interleaved, blocked, or simultaneous multithreading. A multithreaded microprocessor typically allows the multiple threads to share the functional units of the microprocessor (e.g., instruction fetch and decode units, caches, branch prediction units, and load/store, integer, floating-point, SIMD, etc. execution units) in a concurrent fashion. However, multithreaded microprocessors include multiple sets of resources, or contexts, for storing the unique state of each thread, such as multiple program counters and general purpose register sets, to facilitate the ability to quickly switch between threads to fetch and issue instructions.
One example of a performance-constraining issue addressed by multithreading microprocessors is the fact that accesses to memory outside the microprocessor that must be performed due to a cache miss typically have a relatively long latency. It is common for the memory access time of a contemporary microprocessor-based computer system to be between one and two orders of magnitude greater than the cache hit access time. Consequently, while the pipeline is stalled waiting for the data from memory, some or all of the pipeline stages of a single-threaded microprocessor may be idle performing no useful work for many clock cycles. Multithreaded microprocessors may solve this problem by issuing instructions from other threads during the memory fetch latency, thereby enabling the pipeline stages to make forward progress performing useful work, somewhat analogously to, but at a finer level of granularity than, an operating system performing a task switch on a page fault. Other examples are pipeline stalls and their accompanying idle cycles due to a branch misprediction and concomitant pipeline flush, or due to a data dependence, or due to a long latency instruction such as a divide instruction. Again, the ability of a multithreaded microprocessor to issue instructions from other threads to pipeline stages that would otherwise be idle may significantly reduce the time required to execute the program or collection of programs comprising the threads. Another problem, particularly in embedded systems, is the wasted overhead associated with interrupt servicing. Typically, when an input/output device signals an interrupt event to the microprocessor, the microprocessor switches control to an interrupt service routine, which requires saving of the current program state, servicing the interrupt, and restoring the current program state after the interrupt has been serviced. A multithreaded microprocessor provides the ability for event service code to be its own thread having its own context. Consequently, in response to the input/output device signaling an event, the microprocessor can quickly—perhaps in a single clock cycle—switch to the event service thread, thereby avoiding incurring the conventional interrupt service routine overhead.
Just as the degree of instruction-level parallelism dictates the extent to which a microprocessor may take advantage of the benefits of pipelining and superscalar instruction issue, the degree of thread-level parallelism dictates the extent to which a microprocessor may take advantage of multithreaded execution. An important characteristic of a thread is its independence of the other threads being executed on the multithreaded microprocessor. A thread is independent of another thread to the extent its instructions do not depend on instructions in other threads. The independent characteristic of threads enables the microprocessor to execute the instructions of the various threads concurrently. That is, the microprocessor may issue instructions of one thread to execution units without regard for the instructions being issued of other threads. To the extent that the threads access common data, the threads themselves must be programmed to synchronize data accesses with one another to insure proper operation such that the microprocessor instruction issue stage does not need to be concerned with the dependences.
As may be observed from the foregoing, a processor concurrently executing multiple threads may reduce the time required to execute a program or collection of programs comprising the multiple threads. However, there is an overhead associated with the creation and dispatch of a new thread of execution. That is, the microprocessor must expend useful time performing the necessary functions to create a new thread—typically allocating context for the new thread and copying the parent thread's context to the new thread's context—and scheduling the new thread for execution, i.e., determining when the microprocessor will begin to fetch and issue instructions from the new thread. The overhead time is analogous to the task-switching overhead of a multitasking operating system and does not contribute to performing the actual task to be accomplished by the program or collection of programs, such as multiplying matrices or processing a packet received from a network or rendering an image. Consequently, although in theory executing multiple threads in parallel may improve the microprocessor's performance, the extent of the performance improvement is limited by the overhead of creating a new thread. Stated alternatively, the larger the thread creation overhead, the greater the amount of useful work that must be performed by the new thread to amortize the cost of the thread creation. For threads that have a relatively large execution time, the thread creation overhead may be essentially irrelevant to performance. However, some applications may benefit from threads with relatively short execution times that are created relatively frequently, in which case the thread creation overhead must be small in order to realize substantial performance gains from multithreading. Therefore, what is needed is a multithreaded microprocessor having in its instruction set a lightweight thread creation instruction.